/*! \file grid.h
	\author Many
	Класс получения пути среди блоков и линий
*/
#ifndef GRID_H
#define GRID_H
#include <QPointF>
#include <QRectF>
#include <QLineF>
#include <QList>
#include <QVector>

/*! \class GridPoint
    \brief Класс узла сети
*/
class GridPoint : public QPointF
{
private:
    QList<GridPoint *> neighbors;   //!< Соседние точки
    GridPoint *        previous;    //!< Previous point from point
    bool               separated;   //!< Whether the point is separated (TODO: Translate this to russian)

public:
    /*! Конструирует точку сети из другой точки
		\param[in]  p  точка, из которой копируются координаты   
	*/
    inline GridPoint(const QPointF & p) : QPointF(p) {separated=false; previous=NULL; }
    /*! Tests, whether point is separated
     */
    inline bool isSeparated()  { return separated; }
    /*! Sets separated flag
     */
    inline void separate() { separated=true; }
    /*! Деструктор
    */
    inline ~GridPoint() {}
    /*! A distance from one distance
     */
    float dist(GridPoint * g);  //!< A distance to other point
    /*! Computes a distance from this node to start
     */
    float g();
    /*! Computes a heuristic function to finish
     */
    float h(GridPoint * goal);
    /*! Computes a common heuristic function (g+h)
     */
    float f(GridPoint * goal);
    /*! Returns previous point
     */
    inline GridPoint * getPrevious() {return previous; }
    /*! Sets a previous point
     */
    inline void setPrevious(GridPoint * p) { previous=p;}
    /*! Возвращает число соседних точек
                \return число соседних точек
    */
    inline int neighborsCount() const { return neighbors.count(); }
    /*! Возвращает соседнюю точку
		\param[in]  i номер точки
		\return     указатель на точку
    */
    inline GridPoint * operator[](int i) { return neighbors[i]; }
    /*! Добавление нового соседа
                \param[in] n  новая точка
    */
	void addNeighbor(GridPoint* n); 
    /*! Удаление соседней точки из списка
		\param[in]  n   точка
    */
    inline void removeNeighbor(GridPoint* n){ neighbors.removeAll(n); }


    /*! Точка, лежащая выше этой.
        \return     указатель на точку, лежащую выше
    */
	inline GridPoint * north(){ 
		for (int i = 0; i < neighbors.size(); i++) 
			if (neighbors[i]->y() < y()) 
				return neighbors[i]; 
		return NULL ;
	}

        /*! Точка, лежащая ниже этой.
            \return     указатель на точку, лежащую ниже
        */
	inline GridPoint * south(){ 
		for (int i = 0; i < neighbors.size(); i++) 
			if (neighbors[i]->y() > y()) 
				return neighbors[i]; 
		return NULL ;
	}

        /*! Точка, лежащая правее этой.
            \return     указатель на точку, лежащую правее
        */
	inline GridPoint * west(){ 
		for (int i = 0; i < neighbors.size(); i++) 
			if (neighbors[i]->x() > x()) 
				return neighbors[i]; 
		return NULL ;
	}

        /*! Точка, лежащая левее этой.
            \return     указатель на точку, лежащую левее
        */
	inline GridPoint * east(){ 
		for (int i = 0; i < neighbors.size(); i++) 
			if (neighbors[i]->x() < x()) 
				return neighbors[i]; 
		return NULL ;
        }
};

typedef QVector<QPointF> Polyline;

/*! \class Grid
    \brief Класс сети, которая осуществляет построение.
*/
class Grid
{
private:
    bool            built;                  //!< Whether grid is built
    QRectF          bounds;                 //!< Границы сети
    QList<QRectF>   blocks;                 //!< Блоки-препятствия
    QList<QLineF>   gridHLines;             //!< Горизонтальные линии сети
    QList<QLineF>   gridVLines;             //!< Вертикальные линии сети
    QList< QList<GridPoint*> > gridPoints;   //!< Узлы сети

    QPointF start;                          //!< Начальная точка пути
    QPointF goal;                           //!< Конечная точка пути

    GridPoint* g_start;                     //!< Начальная точка пути
    GridPoint* g_goal;                      //!< Конечная точка пути

    float margin;                           //!< Значение отступа между границами блоков

    QVector<Polyline> * polylines;          //!< Current optimized polylines

    /*! Tries optimization of polyline
     */
    void tryOptimize(const Polyline & p);
    /*! Determines, whether line intersects with blocks
     */
    bool intersects(const QPointF & start, const QPointF & end);
    /*! Determines, whether polyline intersects with blocks
     */
    bool intersects(const QVector<QPointF> & line);
    /*! Adds a point to open list
        \param[out] open open list
        \param[in] point new point
        \param[in]  cur  current point
     */
    void addToOpenList(QVector<GridPoint *> & open, GridPoint * point,GridPoint * cur);
    /*! Determines  whethr point is within rectangle
     */
    bool isWithinPoint(const QPointF & p);

    /*! Строит сеть по заданным блокам
    */
    void build();                        
    /*! Ищет неоптимизированный путь из начала в конец
                \return путь, если он существует, иначе пустой вектор
    */
    QVector<QPointF>  getRoughPath();                        
    /*! Оптимизирует путь 
		\param[in] path путь
		\return оптимизированный путь
    */
    QVector<QPointF>  optimizePath(const QVector<QPointF> & path);
    /*! Создает горизонтальную линию сетки с заданой координатой y
                \param[in] y координата
                \return новая горизонтальная линия
    */


    inline QLineF makeHLine(float y)
    {return QLineF(QPointF(bounds.left(),y),QPointF(bounds.right(),y));}
    /*! Создает вертикальную линию сетки с заданой координатой x
                \param[in] x координата
                \return новая вертикальная линия
    */
    inline QLineF makeVLine(float x)
    {return QLineF(QPointF(x,bounds.top()),QPointF(x,bounds.bottom()));}
    /*! Возвращает TRUE если линия line пересекает прямоугольник rect
                \param[in] line линия
                \param[in] rect прямоугльник
                \return TRUE если линия пересекает прямоугольник, иначе FALSE
    */
    inline  bool intersects(QLineF line, QRectF rect){
		bool crossBorders = (line.intersect(QLineF(rect.topLeft(),rect.topRight()),NULL) == QLineF::BoundedIntersection) 
		||(line.intersect(QLineF(rect.topLeft(),rect.bottomRight()),NULL) == QLineF::BoundedIntersection)
		|| (line.intersect(QLineF(rect.bottomRight(),rect.topRight()),NULL) == QLineF::BoundedIntersection)
		|| (line.intersect(QLineF(rect.bottomRight(),rect.bottomLeft()),NULL) == QLineF::BoundedIntersection);
		bool isWithin = rect.contains(line.p1()) || rect.contains(line.p2());
		return crossBorders || isWithin;
    }
    /*! Соединяет точки(взаимное добавление в соседи), если они достижимы друг из друга
        \param[in] p1 point1
        \param[in] p2 point2
     */
    void connectIfReachable(GridPoint * p1,GridPoint * p2);
public:
    /*!  Конструктор
    */
    /*! Конструирует пустую сеть с заданными точками поиска пути от начала до конца
                \param[in] _start  начальная точка
                \param[in] _goal   конечная  точка
                \param[in] _margin отступы
                \param[in] _sceneRect прямоугольник, описывающий края сцены
                \param[in] _scenemargin отступы от прямоугольника сцены
    */
    inline Grid(const QPointF & _start,
                const QPointF & _goal,
                float _margin,
                const QRectF  & _sceneRect,
                float _scenemargin
                )
    {
                 start=_start; goal=_goal; margin=_margin;
                 bounds=_sceneRect;
				 bounds.setTopLeft (bounds.topLeft()+QPointF(_scenemargin,_scenemargin));
				 bounds.setBottomRight (bounds.bottomRight()-QPointF(_scenemargin,_scenemargin));
				 g_start = g_goal = NULL;
                 built=false;
    }
    /*! Добавляет прямоугольник
		\param[in] rect прямоугольник
    */
    inline void pushRect(const QRectF & rect) { blocks<<rect;}
    /*! Добавляет линию
                \param[in] p1   точка начала
                \param[in] p2   точка конца
    */
    inline void pushLine(const QPointF & p1, const QPointF & p2)
    { if (p1.x()==p2.x()) gridVLines<<QLineF(p1,p2);
      else if (p1.y() == p2.y()) gridHLines<<QLineF(p1,p2);
    }
    /*!  Деструктор
    */
    ~Grid();
    /*! Ищет путь из точки начала в точку конца, оптимизируя его
                \return путь, если он существует, иначе пустой вектор
    */
    QVector<QPointF>  getPath();

    friend class testwindow;
};
#endif // GRID_H
